/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.hidden;

import java.util.BitSet;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Block;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Column;
import com.onegravity.sudoku.solver.data.ExtraRegionExtended;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.Region;
import com.onegravity.sudoku.solver.data.Row;
import com.onegravity.sudoku.solver.util.CommonTuples;
import com.onegravity.sudoku.solver.util.Permutations;

/**
 * Implementation of hidden set solving techniques
 * (Hidden Pair, Hidden Triplet, Hidden Quad).
 * <p>
 * Only used for degree 2 and below. Degree 1 (hidden single)
 * is implemented in {@link com.onegravity.sudoku.solver.rules.hidden.HiddenSingleProducer}.
 */
public class HiddenSubsetProducer implements IndirectHintProducer {

	private final int degree;

    public HiddenSubsetProducer(int degree) {
        this.degree = degree;
    }

    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        if (grid.hasExtraRegions()) {
        	getHints(grid, ExtraRegionExtended.class, accu);
        }
        getHints(grid, Block.class, accu);
        getHints(grid, Column.class, accu);
        getHints(grid, Row.class, accu);
    }

    /**
     * For each parts of the given type, check if a n-tuple of cells have
     * a common n-tuple of potential values, and no other potential value.
     * @param regionType the type of the parts to check
     * @param degree the degree of the tuples to search
     * @throws InterruptedException 
     */
    private <T extends Region> void getHints(Grid grid, Class<T> regionType, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        Region[] regions = grid.getRegions(regionType);
        Permutations perm = new Permutations(degree, 9);
        BitSet[] potentialIndexes = new BitSet[degree];

        // Iterate on parts
        for (Region region : regions) {
            int nbEmptyCells = region.getEmptyCellCount();
            if (nbEmptyCells > degree * 2) {
                // Iterate on tuple of values
            	perm.reset();
                while (perm.hasNext()) {
                    if (Thread.interrupted()) throw new InterruptedException();
                    int[] values = perm.nextBitNums();

                    // Build the value tuple
                    for (int i = 0; i < values.length; i++) {
                        values[i] += 1; // 0..8 -> 1..9
                    }

                    // Build potential positions for each value of the tuple
                    for (int i = 0; i < degree; i++) {
                    	if (potentialIndexes[i]==null) potentialIndexes[i] = new BitSet(10);
                        region.getPotentialPositions(potentialIndexes[i], values[i]);
                    }

                    // Look for a common tuple of potential positions, with same degree
                    BitSet commonPotentialPositions = CommonTuples.searchCommonTuple(potentialIndexes, degree);
                    if (commonPotentialPositions != null) {
                        // Hint found
                        IndirectHint hint = createHiddenSetHint(region, values, commonPotentialPositions);
                        if (hint!=null && hint.isWorth()) accu.add(hint);
                    }
                }
            }
        }
    }

    private IndirectHint createHiddenSetHint(Region region, int[] values, BitSet commonPotentialPositions) {
        // Create set of fixed values, and set of other values
        BitSet valueSet = new BitSet(10);
        for (int i = 0; i < values.length; i++) {
            valueSet.set(values[i], true);
        }

        Cell[] cells = new Cell[degree];
        int dstIndex = 0;
        // Look for concerned potentials and removable potentials
        Map<Cell,BitSet> cellPValues = new LinkedHashMap<Cell,BitSet>();
        Map<Cell,BitSet> cellRemovePValues = new HashMap<Cell,BitSet>();
        for (int index = 0; index < 9; index++) {
            Cell cell = region.getCell(index);
            if (commonPotentialPositions.get(index)) {
                cellPValues.put(cell, valueSet);
                // Look for the potential values we can remove
                BitSet removablePotentials = null;
                for (int value = 1; value <= 9; value++) {
                    if (!valueSet.get(value) && cell.hasPotentialValue(value)) {
                    	if (removablePotentials==null) removablePotentials = new BitSet(10);
                    	removablePotentials.set(value);
                    }
                }
                if (removablePotentials!=null && !removablePotentials.isEmpty()) {
                	cellRemovePValues.put(cell, removablePotentials);
                }
                cells[dstIndex++] = cell;
            }
        }
        
        return (!cellRemovePValues.isEmpty()) ? new HiddenSubsetHint(cells, values, cellPValues, cellRemovePValues, region) : null;
    }

	@Override
	public String getProducerName() {
		int id = R.string.producer_hidden_pair;
		switch(degree) {
		case 2: id =  R.string.producer_hidden_pair; break;
		case 3: id =  R.string.producer_hidden_triple; break;
		case 4: id =  R.string.producer_hidden_quad; break;
		}
		return HintResource.getString(id);
	}
}